package algorithms.leecode;

import cn.hutool.core.collection.CollectionUtil;

import java.util.*;

//广度优先
public class Au126 {
    public static void main(String[] args) {
        String beginword = "hit";
        String endword = "tax";
        String[] s = {"ted", "tex", "tax", "tad","red", "den", "rex", "pee"};
        List<String> wordList = new ArrayList<>(Arrays.asList(s));
        List<List<String>> ladders = findLadders(beginword, endword, wordList);
        System.err.println(ladders);
    }

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> sSet = new HashSet<>();
        for (int i = 0; i < wordList.size(); i++) {
            sSet.add(wordList.get(i));
        }

        List<List<String>> result = new ArrayList<>();
        List<String> list = new ArrayList<>();
        list.add(beginWord);
        List<List<String>> list1 = new ArrayList<>();
        list1.add(list);


        sfs(sSet, endWord, list1, result);
        return result;
    }

    public static void sfs(Set<String> set, String endWord, List<List<String>> stringList, List<List<String>> result) {
        List<String> s = new ArrayList<>();

        List<List<String>> rsList = new ArrayList<>();
        for (String string : set) {
                for (List<String> list : stringList) {
                    List<String> strList = new ArrayList<>(list);
                // 如果结束
                String string2 = strList.get(strList.size() - 1);

                if (canBe(string, string2)) {
                    strList.add(string);
                    if (string.equals(endWord)) {
                        result.add(strList);
                    }
                    // 如果未结束
                    s.add(string);
                    rsList.add(strList);
                }


            }


        }
        // 如果无匹配则直接结束
        if (CollectionUtil.isEmpty(s)) {
            return;
        }
        set.removeAll(s);

        Set<String> endSet = new HashSet<>(set);
        sfs( endSet, endWord, rsList, result);
    }

    public static boolean canBe(String target, String s) {
        if (s.length() != target.length()) {
            return false;
        }
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (target.charAt(i) != s.charAt(i)) {
                count++;
            }
        }
        if (count > 1) {
            return false;
        }

        return true;
    }




}
